//785 Is Graph Bipartite
/*
给定一个图，判断其是否可以二分

输入是邻接链表表示的图（如位置 0 的邻接链表为 [1,3]，表示 0 与 1、 0 与 3 相连）；输出是
一个布尔值，表示图是否二分
Input: [[1,3], [0,2], [1,3], [0,2]]
0----1
|	 |
|	 |
3----2
Output: true
*/
bool isBipartite(vector<vector<int>>& graph) {
	int n = graph.size();
	if (n == 0) {
		return true;
	}
	vector<int> color(n, 0);
	queue<int> q;
	for (int i = 0; i < n; ++i) {
		if (!color[i]) {
			q.push(i);
			color[i] = 1;
		}
		while (!q.empty()) {
			int node = q.front();
			q.pop();
			for (const int & j : graph[node]) {
				if (color[j] == 0) {
					q.push(j);
					color[j] = color[node] == 2 ? 1 : 2;
				}
				else if (color[node] == color[j]) {
					return false;
				}
			}
		}
	}
	return true;
}

